package com.ftx.service.algorithm.binaryTree;

import javax.validation.constraints.Max;
import java.util.*;

/**
 * Created by tangwenru on 2022/6/12.
 */
public class BinaryTreeTraverse {

    public static void main(String[] args) {
        BinaryTreeTraverse treeTraverse = new BinaryTreeTraverse();
//        treeTraverse.postOrder(treeTraverse.buildRoot());
//        treeTraverse.postOrderIter(treeTraverse.buildRoot());
        int sum = treeTraverse.diameterOfBinaryTree(treeTraverse.buildRoot());
        System.out.println(sum);
//        for (StringBuilder stringBuilder : treeTraverse.result) {
//            System.out.println(stringBuilder.toString());
//        }
    }


    public TreeNode buildRoot() {
        TreeNode root = new TreeNode(1);
        root.left = new TreeNode(2);
        root.left.left = new TreeNode(3);
        root.left.right = new TreeNode(4);
        root.right = new TreeNode(5);
        return root;
    }

    class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }


    /**
     * 前序遍历  根 -> 左 -> 右
     * 结果：12345
     */
    public void preOrder(TreeNode tree) {
        if (tree == null) {
            return;
        }
        System.out.print(tree.val);
        preOrder(tree.left);
        preOrder(tree.right);
    }

    //使用栈实现非递归算法
    //java 中使用 Deque， Stack已经弃用。
    //Deque 的使用用法：push、pop。
    public void perOrderIter(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        stack.push(root);
        while (!stack.isEmpty()) {
            TreeNode treeNode = stack.pop();
            result.append(treeNode.val);
            if (treeNode.right != null) {
                stack.push(treeNode.right);
            }
            if (treeNode.left != null) {
                stack.push(treeNode.left);
            }
        }
        System.out.println(result.toString());
    }


    /**
     * 中序遍历  左 -> 根 -> 右
     * 结果：32415
     */
    public void midOrder(TreeNode tree) {
        if (tree == null) {
            return;
        }
        midOrder(tree.left);
        System.out.print(tree.val);
        midOrder(tree.right);
    }

    /**
     * 迭代式中序遍历  左 -> 根 -> 右
     * 这个比较难，重点关注一下。
     */
    public void minOrderIter(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        while (root != null || !stack.isEmpty()) {

            //此处的目的是放入将根节点放入，然后将根节点的左节点压在根节点上面。
            while (root != null) {
                stack.push(root);
                root = root.left;
            }
            //调出栈
            root = stack.pop();
            result.append(root.val);
            root = root.right;
        }
        System.out.println(result.toString());
    }

    /**
     * 后序遍历  左 -> 右 -> 根
     * 结果：34251
     */
    public void postOrder(TreeNode tree) {
        if (tree == null) {
            return;
        }
        postOrder(tree.left);
        postOrder(tree.right);
        System.out.print(tree.val);
    }

    /**
     * 迭代式后序遍历
     * 后序遍历更复杂！！！！
     * 先遍历左节点 -> 右节点 -> 根节点
     * 1
     * / \
     * 2   5
     * / \
     * 3   4
     * / \
     * 7   8
     */
    public void postOrderIter(TreeNode root) {
        if (root == null) {
            return;
        }
        Deque<TreeNode> stack = new ArrayDeque<>();
        StringBuilder result = new StringBuilder();
        TreeNode pre = null; //记录前置节点
        while (root != null || !stack.isEmpty()) {
            //把所有的左子树节点都放入栈中
            while (root != null) {
                stack.push(root);
                root = root.left;
            }

            //找到当前节点
            root = stack.pop();
            //如果当前节点的右节点为空
            //这里为什么会有对pre的判断，是为了避免重复处理。
            //拿例子：当8已经处理完了之后，应该处理4节点，当时发现4也是有右子树的，但是8已经处理过了，通过pre达标，那么8也不用处理。
            if (root.right == null || pre == root.right) {
                result.append(root.val);
                //设置前置节点
                pre = root;
                //置为空的目的是处理栈中堆积的父节点。
                root = null;
            } else {
                //右节点非空,说明当前节点这个时候不能够处理,就把当前节点再放回去。
                stack.push(root);
                //把当前节点的右节点作为root进行处理。
                root = root.right;
            }
        }
        System.out.println(result.toString());
    }


    /**
     * 层级遍历
     * 递归的方式
     * 递归需要存储每个的层级 对应的数据都有什么，借助额外的数据结构
     */
    public List<StringBuilder> result = new ArrayList<>();

    public void levelOrder(TreeNode root, int level) {
        if (root == null) {
            return;
        }
        //当数组大小等于层级时，初始化该层级需要的存储空间
        if (result.size() == level) {
            StringBuilder stringBuilder = new StringBuilder();
            stringBuilder.append(root.val);
            result.add(level, stringBuilder);
        } else {
            result.get(level).append(root.val);
        }
        levelOrder(root.left, level + 1);
        levelOrder(root.right, level + 1);
    }

    /**
     * 迭代式层级遍历
     * 借助额外的数据结构：队列，特性：先进先出
     * queue 的基本用法：add(offer)，remove(poll)
     */
    public void levelOrderIter(TreeNode root) {
        if (root == null) {
            return;
        }
        StringBuilder result = new StringBuilder();
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            result.append(current.val);
            if (current.left != null) {
                queue.add(current.left);
            }
            if (current.right != null) {
                queue.add(current.right);
            }
        }
        System.out.println(result.toString());
    }


    /**
     * 打印每个二叉树的层级 按层打印
     */
    public void levelOrderIterByLevel(TreeNode root) {
        if (root == null) {
            return;
        }
        StringBuilder result = new StringBuilder();
        // 当前行打印的最右节点
        TreeNode last = root;
        // 下一行打印的最右节点
        TreeNode nextLast = null;
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while (!queue.isEmpty()) {
            TreeNode current = queue.poll();
            result.append(current.val);
            if (current.left != null) {
                queue.add(current.left);
                nextLast = current.left; //如果当前节点的left非空，则认为下一层的next是当前节点的left
            }
            if (current.right != null) {
                queue.add(current.right);
                nextLast = current.right; //同理
            }
            //若是发现当前层的最后一个节点同当前节点相同，则打印
            if (last == current) {
                result.append("\\n");
                //将下一层的最后一个节点赋值到当前层的最后一个节点用于下一次循环
                last = nextLast; //
            }
        }
        System.out.println(result.toString());
    }

    /**
     * 236. 二叉树的最近公共祖先
     * https://leetcode.cn/problems/lowest-common-ancestor-of-a-binary-tree/
     *      1
     *      / \
     *     2   5
     *    / \
     *   3   4
     *      / \
     *     7   8
     * 题目分析：
     * 比如，想要求 2,5的公共祖先，那么就需要知道哪个父节点可以到达2,5
     * 同理,想要求 3,5的公共祖先，那么就需要知道哪个父节点可以到达3,5
     *
     *
     */
    public TreeNode lowestCommonAncestor(TreeNode root, TreeNode p, TreeNode q) {

        return null;
    }



    /**
     * 二叉树的直径
     * 给定一棵二叉树，你需要计算它的直径长度。一棵二叉树的直径长度是任意两个结点路径长度中的最大值。这条路径可能穿过也可能不穿过根结点。
     */
    public int diameterOfBinaryTree(TreeNode root) {
        /**
         *            1
         *          / \
         *        2    3
         *       / \  /
         *     4   5 6
         * 已此为例，我们想求最大直径，也就是3->4 的距离，那么就是节点1 左子节点和右子节点的深度
         * 虚拟公式：
         * depth（1） = depth(2)+depth(3)
         *
         *
         */
        depth(root);
        return MAX;
    }

    /**
     * 在获取二叉树深度的过程中，已经知道了左子树和右子树的深度，所以执行的过程中可以知道叶子节点间的最大长度。
     */
    public int MAX = 0 ;
    public int depth(TreeNode root){
        if (root == null){
            return 0;
        }
        int leftDepth = depth(root.left);
        int rightDepth = depth(root.right);
        int sum = leftDepth + rightDepth;
        if (sum > MAX){
            MAX = sum;
        }
        return Math.max(leftDepth,rightDepth)+1;
    }

}
